295. Круг

 

Сколько точек с целочисленными координатами находится в круге радиусом r? Точка, находящаяся на окружности, считается принадлежащей кругу. Центр круга имеет целочисленные координаты.

 

Вход. Целочисленный радиус окружности r (r ≤ 15000).

 

Выход. Вывести искомое количество точек.

 

Пример входа

Пример выхода

2

13

 

 

РЕШЕНИЕ

цикл двойной

 

Анализ алгоритма

Разобьем множество точек с целочисленными координатами на пять частей как показано слева на рисунке: одна точка лежит в центре, остальные четыре множества равны между собой и покрывают четыре части круга. Если количество точек, лежащих в первой четверти, равно res, то общее количество точек в круге равно 4 * res + 1.

  

 

Для вычисления значения res следует найти такое количество пар целых чисел (i, j) что 0 ≤ i ≤ r и  1 ≤ j ≤ r. Это можно сделать при помощи двойного цикла за O(r2).

Рассмотрим алгоритм нахождения res за O(r). На оси y = k (0 ≤ k ≤ r) внутри круга лежит в точности  целочисленных точек. Следовательно общее число точек res в первой четверти равно

 

Реализация алгоритма – O(r2)

Читаем радиус окружности r.

 

res = 0;

scanf("%d",&r);

 

Подсчитываем количество целочисленных точек в первой четверти.

 

for(i = 0; i <= r; i++)

for(j = 1; j <= r; j++)

  if(i*i + j*j <= r*r) res++;

 

Выводим ответ.

 

printf("%d\n",res * 4 + 1);

 

Реализация алгоритма – O(r)

 

#include <stdio.h>

#include <math.h>

 

int r, y, res;

double r2;

 

int main(void)

{

  scanf("%d",&r);

  res = 0; r2 = r*r;

  for(y = 0; y <= r; y++)

    res += (int)sqrt(r2 - y*y);

  res = 4 * res + 1;

  printf("%d\n",res);

  return 0;

}

 

Java реализация – O(r2)

 

import java.util.*;

 

public class Main

{

  public static void main(String[] args)

  {

    Scanner con = new Scanner(System.in);

    int r = con.nextInt();

    int res = 0;

    for(int i = 0; i <= r; i++)

    for(int j = 1; j <= r; j++)

      if(i * i + j * j <= r * r) res++;

 

    System.out.println(res * 4 + 1);

    con.close();

  }

}

 

Java реализация – O(r)

 

import java.util.*;

 

public class Main

{

  public static void main(String[] args)

  {

    Scanner con = new Scanner(System.in);

    int r = con.nextInt();

    int res = 0, r2 = r*r;

 

    for(int y = 0; y <= r; y++)

      res += (int)Math.sqrt(r2 - y*y);

    res = 4 * res + 1;

   

    System.out.println(res);

    con.close();

  }

}

 

Python реализация – O(r2)

 

r = int(input())

res = 0

for i in range(r+1):

  for j in range(1,r + 1):

    if i * i + j * j <= r * r: res += 1

 

res = res * 4 + 1

print(res)

 

Python реализация – O(r)

 

import math

 

r = int(input())

res = 0

r2 = r*r

for y in range(r + 1):

  res += (int)(math.sqrt(r2 - y*y))

 

res = res * 4 + 1

print(res)